def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        def matches(i: int, j: int) -> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]

        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] |= f[i][j - 2]
                    if matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

# 记word1的长度为 m，word2的长度为 n 为便于状态更新，减少对边界的判断，初始二维 dp 数组维度为 {(m+1) \times(n+1)}(m+1)×(n+1) ，其中第一行和第一列的状态分别表示字符串word1和word2为空时的情况。
class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """

        m, n = len(word1), len(word2)
        if m * n == 0:  # word1鎴杦ord2涓虹┖
            return m + n

        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 边界状态
        for i in range(1, m + 1):
            dp[i][0] = i
        for j in range(1, n + 1):
            dp[0][j] = j

        # 状态更新
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

        return dp[m][n]
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        n = len(triangle)
        # dp[i][j] 表示从 triangle[i][j] 出发，自顶向下的最小路径和
        dp = [[0] * n for _ in range(n)]
        dp[0][0] = triangle[0][0]
        for i in range(1, n):
            for j in range(i+1):
                if j == 0:  # 最左侧的点，只能从上一层的最左侧点过来
                    dp[i][j] = dp[i-1][j] + triangle[i][j]
                elif j == i:  # 最右侧的点，只能从上一层的最右侧点过来
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j]
                else:  # 其他点，可以从上一层相邻的两个点中的任意一个过来
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
        return min(dp[n-1])


def trap( height) -> int:
    sum = 0
    n = len(height)
    leftList = [height[0]] + [0] * (n - 1)
    rightList = [0] * (n - 1) + [height[n - 1]]
    for i in range(1,n):
        leftList[i]=max(leftList[i-1],height[i-1])
    for i in range(n-2,-1,-1):
        rightList[i]=max(rightList[i+1],height[i+1])
    for i in range(1, len(height) - 1):
        m = (min(leftList[i], rightList[i]) - height[i])
        if m > 0:
            sum += m
    return sum


class Solution:
    def uniquePaths(self, m, n) :
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

